﻿//【初阶】30.map+set
//【头文件包含】
//C++的主要头文件
#include<iostream>//c++的输入输出流
using namespace std;
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
//C的主要头文件
//#include<stdio.h>
//#include<stdlib.h>
//#include<assert.h>
//#include<string.h> 
#include"AVLTree.hpp"



//【命名空间】

//【结构体声明】【类声明】
//【函数声明】
void Test1();void Test2();void Test3();void Test4(); void Test5();


//【主函数】
int main()
{
	Test1();
	Test2();
	Test3();
	Test4();
	Test5();
	
	TestAVLTree1();

	cout << "****主函数结束****" << endl;
	return 0;
}

//【函数定义】


/*测试用例*/void Test1()
{
	cout << "****测试用例开始****"<< endl;
	std::string strs[] = { "find","cur","std","map","set","set","map","string","map","cur" };
	std::map<std::string, int> countmap;
	for (auto& a : strs)
	{
		std::map<std::string, int>::iterator ret = countmap.find(a);
		if (ret != countmap.end())
		{
			ret->second++;
		}
		else
		{
			countmap.insert(make_pair(a, 1));
		}
	}
	for (auto& a : countmap)
	{
		cout << a.first << ":" << a.second << endl;
	}
	cout << endl;
	cout << "****测试用例结束****" << endl << endl;
}

/*测试用例*/void Test2()
{
	cout << "****测试用例开始****" << endl;
	std::string strs[] = { "find","cur","std","map","set","set","map","string","map","cur" };
	std::map<std::string, int> countmap;
	for (auto& a : strs)
	{
		countmap[a]++;
	}
	for (auto& a : countmap)
	{
		cout << a.first << ":" << a.second << endl;
	}
	cout << "****测试用例结束****" << endl<<endl;
}

/*测试用例*/void Test3()
{
	cout << "****测试用例开始****" << endl;
	std::string strs[] = { "find","cur","std","map","set","set","map","string","map","cur" };
	std::map<std::string, int> countmap;
	for (auto& a : strs)
	{
		//利用但元素插入版本的insert，返回值时一个包含该map迭代器和bool值的pair，用ret接收
		// 当插入成功，返回pair（map中插入元素的位置，true）
		pair<std::map<std::string, int>::iterator,bool>ret=countmap.insert(make_pair(a, 1));
		// 当插入失败，返回pair（map中已存在的key的位置，false）
		if (ret.second == false)
		{
			//key的位置的迭代器表示key位置的指针
			//使用->可以找到该位置pair类型对象的second成员即计数用的value
			ret.first->second++;
		}
	}
	for (auto& a : countmap)
	{
		cout << a.first << ":" << a.second << endl;
	}
	cout << "****测试用例结束****" << endl << endl;
}

/*测试用例*/void Test4()
{
	cout << "****测试用例开始****" << endl;
	multiset<int> mlts;
	mlts.insert(3);
	mlts.insert(2);
	mlts.insert(3);
	mlts.insert(1);
	mlts.insert(4);
	mlts.insert(5);
	mlts.insert(1);
	for (auto a : mlts)
	{
		cout << a << " ";
	}
	cout << endl;
	cout << "****测试用例结束****" << endl << endl;
}

/*测试用例*/void Test5()
{
	cout << "****测试用例开始****" << endl;
	multimap<string,int> mltm;
	mltm.insert(pair<string, int>("direct", 1));
	mltm.insert(pair<string, int>("direct", 2));
	mltm.insert(pair<string, int>("direct", 3));

	for (auto a : mltm)
	{
		cout << a.first << ":"<<a.second<<" ";
	}
	cout << endl;
	cout << "****测试用例结束****" << endl << endl;
}


//【笔记】
//【初阶】30.map+set
//map和set
	//map的 operator[]  
		//map对象方括号内传入k，返回k值对应的value的引用
		// 底层调用的是insert来实现的 (*((this->insert(make_pair(k,mapped_type()))).first)).second
		//insert在使用时会传一个返回值出来，pair<iterator,bool> insert (const value_type& val);
		// 该版本的insert说明如下
		// The single element versions (1) return a pair, with its member pair::first set to an iterator pointing to
		// either the newly inserted element or to the element with an equivalent key in the map. 
		// The pair::second element in the pair is set to true if a new element was inserted 
		// or false if an equivalent key already existed.
		// 翻译：
		// 单个元素版本（1）的insert返回值类型是pair<iterator,bool>类型，
		// 该pair的first成员是一个迭代器该迭代器指向map中新插入该元素的位置或指向被插入map中与该元素值相等的key值的位置
		// 该pair的second成员有两种状态，当新插入元素被成功插入，则为true，当map中已存在与该元素值相同的key则为false
	//回到mapped_type& operator[] (const key_type& k);	
		//1.If k matches the key of an element in the container, the function returns a reference to its mapped value.
			// 如果k的key值匹配到map中的key，则函数返回该key值对应的value的引用
		//2.If k does not match the key of any element in the container, the function inserts a new element with that key 
		// and returns a reference to its mapped value.Notice that this always increases the container size by one, 
		// even if no mapped value is assigned to the element(the element is constructed using its default constructor).
			// 如果k值的key没有匹配到map中的key，则该函数会调用一个insert去新插入一个k到map中并返回插入k值对应的value的引用。
			// 需要注意的是，这种操作总会是该map容器的元素大小增加1
			// 即便该k值没有对应的value，也会被分配给一个元素，该元素使用其默认构造函数进行构造
		//3.A similar member function, map::at, has the same behavior when an element with the key exists,
		// but throws an exception when it does not.
			// std还有一个和该函数类似的函数叫做map::at,他们在插入元素已经存在时有同样的表现，
			// 区别在于map::operator[]会调默认构造插入，map::at会抛出异常
		//*.A call to this function is equivalent to :(*((this->insert(make_pair(k, mapped_type()))).first)).second
			// 该函数相当于调用(*((this->insert(make_pair(k, mapped_type()))).first)).second
			//(*((this->insert(make_pair(k, mapped_type()))).first)).second
			//                              mapped_type()                   1.mapped_type()插入map的键值对的V的缺省值
			//                          (k, mapped_type())                  2.k是一个键值对的键值的类型的值
			//                (make_pair(k, mapped_type()))                 3.使用make_pair生成一个含以上两个参数的键值对对象
			//    this->insert(make_pair(k, mapped_type()))                 4.调用该map的insert插入该键值对对象
			//   (this->insert(make_pair(k, mapped_type()))).first          5.返回值类型是pari<iterator,bool>，找到该pair的first即被插位置的迭代器
			// *((this->insert(make_pair(k, mapped_type()))).first)         6.对该迭代器解引用得到map中插入位置的键值对元素
			//(*((this->insert(make_pair(k, mapped_type()))).first)).second 7.找到该键值对元素的对应的second即T，返回的是引用类型
				// 第4步，插入失败，则指向的是同名k的键值对元素位置，则第7步返回的是该键值对元素对应的value引用
				// 第4步，插入成功，则说明原map没有该k的键值对元素，插入的mapped_type类型的元素构造的是一个pair<key,T>
				// key=k,T=mapped_type()其中T为该类型的缺省值
	//综上map::operator[]可以实现插入或插入+修改；
	
	//multiset和multimap,是允许键值冗余的，可以插入重复的key元素 
		//multiset和set类似
		//multimap的insert不存在插入失败，所以没有operator[],因为相同元素返回插入值迭代器不明确
		//set、multiset、map和multimap还可以传一个class Compare = less<Key>的值，默认是按从小到大排序，可以传greater<K>实现从大到小排序
	
	//AVL树：高度平衡的二叉搜索树
		//构成AVL树的条件
			// 整体为搜索二叉树
			// 树的左右子树高度差不超过1，树左右子树内部也满足该要求 
		//为了方便实现该树，引入平衡因子概念（但并非只有该方式可以实现AVL树）
		//每个节点的平衡因子=右子树高度-左子树高度
		//因为AVL树高度可控在O（log_2_N）所以整体s搜索效率可以控制在O（log_2_N）










